home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / answrbok / 4_6.lha / 4_6 / 4_6a.c < prev    next >
Text File  |  1993-08-08  |  1KB  |  64 lines
  1. * Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
  2. * The C++ Answer Book */
  3. * Tony Hansen */
  4. * All rights reserved. */
  5. / quick sort
  6. / Version 1
  7. / Based on "Algorithms" by Robert Sedgewick
  8. / Chapter 9, pp 103-113
  9.  
  10. include <swap.h>
  11.  
  12. / Global variables
  13. tatic int *x;
  14.  
  15. / partition the array into two halves
  16. / after the partition,
  17. / K[left] < ... < K[i] < ... < K[right]
  18. / iqsort will then recursively sort
  19. / K[left] through K[i-1] and
  20. / K[i+1] through K[right]
  21.  
  22. tatic int partition(int left, int right)
  23.  
  24.    int i = left - 1;
  25.    int j = right;
  26.    int v = x[j];
  27.  
  28.    do  {
  29. do  {
  30.     i++;
  31. } while (x[i] < v);
  32.  
  33. do  {
  34.     j--;
  35. } while (j > left && x[j] > v);
  36.  
  37. swap(x[i], x[j]);
  38.    } while (i < j);
  39.  
  40.    swap(x[j], x[i]);
  41.    swap(x[i], x[right]);
  42.    return i;
  43.  
  44.  
  45. / the secondary routine which will
  46. / do the actual sorting
  47. tatic void iqsort(int left, int right)
  48.  
  49.    if (right > left)
  50. {
  51. int i = partition(left, right);
  52. iqsort(left, i-1);
  53. iqsort(i+1, right);
  54. }
  55.  
  56.  
  57. / external entry point
  58. oid qsort1(void *array, unsigned nel,
  59.     unsigned, int (*)(const void*,const void*))
  60.  
  61.    x = (int*)array;    // save global pointer
  62.    iqsort(0, nel-1);
  63.  
  64.